
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>递归函数</title>
</head>
<body>

    <script>
        // 程序调用自身的编程技巧称为递归
        // 递归函数:在函数内部调用函数本身的函数


        // 怎么写递归函数
        // 方法：
        // 1：找临界值：无须计算，即可得出的值：---退出递归的条件
        // 2：这一次和上一次运算的关系   fn和fn-1的关系  
        // 3：假设当前递归函数可以运行，根据上一次调用自身的结果，写出这次运算的结果。  fn= fn-1+..


        // 1+2+...+100
        // function add(n) {
        //     let sum = 0;
        //     for (let i = 1; i <= n; i++) {
        //        sum += i   
        //     }
        //     return  sum
        // }

        // console.log(add(100));
        // console.log(add(10));
        // console.log(add(1000));



        //  f(10) = f(9) + 10  addSum(n) = addSum(n-1) + n  addSum(10) = addSum(9)+10 =addSum(8) + 9 + 10 =addSum(7) + 8 + 9 + 10  = 1+2+3+..+10
        function addSum(n) {
            if (n==1) {
                return 1
            }

            return addSum(n-1)+ n
        }

        console.log(addSum(10));
        console.log(addSum(100));
        console.log(addSum(1000));


        // 传入一个n，打印n个hello world   递归  fn = fn-1 + console.log("hello world")

        function printNum(n) {
            if (n==1) {
                return console.log("hello world");
                
            }

            return printNum(n-1)+ console.log("hello world");
        }

        // console.log(printNum(10));
        console.log(printNum(5));



        
        // 兔子繁殖问题：设有一对新生兔子，从第四个月开始他们每个月月初都生一对兔子,新生的兔子从第四个月月初开始又每个月生一对兔子
        // 	按此规律，并假定兔子没有死亡,n(n <= 20)个月月末共有多少对兔子？
        // 	
        // 	
        // 	
        // 	
        // 	
		// 规律:  月份   	1 	2 	3 	4	5	6	7	8 	9 	10 ...
		// 	   	  兔子      1	1   1   2   3   4	6	9	13	19
		// 	   	  
		// 	   	  



          // 	猴子吃桃问题：猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个，第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃前一天剩下的一半零一个。
        // 到第10天早上想再吃时，见只剩下一个桃子了。求第一天共摘多少个桃子？

            //  (1+1)*2    f(n) = (f(n+1)+1)*2

            // 10   9   8    7   6   5    4    3    2    1  
            // 1    4	10	 22  46  94  190  382  766  1534


            


          // 递归应用场景

            	// 文件深拷贝  递归实现    
                // 数组扁平化  递归实现
                // 深度遍历    树形结构
                // 广度遍历	   树形结构


    </script>
    
</body>
</html>